package NewCoder;

public class BM81 {
    //动态规划
    public int maxProfit (int[] prices) {
        // write code here
        int n=prices.length;
        int[][] dp=new int[n][2];
        dp[0][0]=0;//第一天不持股，总收益为0
        dp[0][1]=-prices[0];//第一天持股，总收益为减去该天的股价
        for(int i=1;i<n;i++){
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);//第i天不持股，有可能是前面的若干天中卖掉了或是还没买，因此收益与前一天相同，也可能是当天卖掉股票，我们选择较大的状态
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);//第i天持股，可能是前几天买的还没卖，因此收益与前一天相同，也有可能是当天买，减去买入的花费
        }
        //最后一天不持股，到该天为止的最大收益
        return dp[n-1][0];
    }


    //贪心
//    public int maxProfit (int[] prices) {
//        // write code here
//        int ans=0;
//        int min=Integer.MAX_VALUE;
//        for(int i=1;i<prices.length;i++){
//            if(prices[i]-prices[i-1]>0){
//                ans+=prices[i]-prices[i-1];
//            }
//        }
//        return ans;
//    }
}
